package DataStructure;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

//LFU缓存
public class LFU<K extends Comparable<K>,V> {
    private final int size;
    private final Map<K,Node<K,V>> cache;
    private final PriorityQueue<Node<K,V>> queryList;
    private long timestamp;//每次访问+1



    public LFU(int size) {
        this.size = size;
        this.cache = new HashMap<>();
        this.queryList = new PriorityQueue<>();
        this.timestamp=0;
    }

    private static class Node<K,V> implements Comparable<Node<K,V>>{
        private final K key;
        private V value;
        public int freq;
        public long lastTime;

        public Node(K key, V value, int freq, long lastTime) {
            this.key = key;
            this.value = value;
            this.freq = freq;
            this.lastTime = lastTime;
        }

        @Override
        public int compareTo(Node<K,V> o) {
            if (this.freq != o.freq) {
                return this.freq - o.freq;
            } else {
                return Long.compare(this.lastTime, o.lastTime);
            }
        }
    }


    public V get(K key) {
        timestamp++;
        if (!cache.containsKey(key)) {
            return null;
        }
        Node<K, V> node = cache.get(key);
        updateNode(node);
        return node.value;
    }

    public void put(K key, V value) {
        timestamp++;
        if (cache.containsKey(key)) {
            Node<K, V> node = cache.get(key);
            node.value = value; // 更新值
            updateNode(node); // 更新节点的频率和时间戳
        } else {
            //移除次数最少的
            if (cache.size() >= size) {
                Node<K, V> old = queryList.poll();
                cache.remove(old.key);
            }
            //添加
            Node<K, V> newNode = new Node<>(key, value, 1, timestamp);
            cache.put(key, newNode);
            queryList.add(newNode);
        }
    }

    // 更新节点的频率和时间戳
    private void updateNode(Node<K, V> node) {
        queryList.remove(node); // 从堆中移除节点
        node.freq++; // 增加频率
        node.lastTime = timestamp; // 更新时间戳
        queryList.add(node); // 重新加入堆
    }

    @Override
    public String toString() {
        return "LFU{" +
                "queryList=" + queryList +
                '}';
    }
}
